/*
https://leetcode.cn/problems/minimum-window-substring/

76. 最小覆盖子串
difficult, 李佳韵 2024.08.29
滑动窗口

*/

#pragma once

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.length(), n = t.length();
        if (m < n) return "";
        if (s == t) return s;

        unordered_map<char, int> ti;
        unordered_map<char, int> w;
        for (char c : t) {
            ti[c]++;
        }
        int left = 0, right = 0;
        int minLength = m + 1;
        int start = 0;
        int count = 0;

        while (right < m) {
            char c = s[right];
            w[c]++;
            if (ti.find(c) != ti.end() && w[c] <= ti[c]) {
                count++;
            }
            while (count == n && left <= right) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }
                char d = s[left];
                w[d]--;
                if (ti.find(d) != ti.end() && w[d] < ti[d]) {
                    count--;
                }
                left++;
            }
            right++;
        }

        return minLength > m ? "" : s.substr(start, minLength);
    }
};

int main() {
    Solution solution;
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << "最小子串为：" << solution.minWindow(s, t) << endl;
    return 0;
}